package com.liyghting.datastructurealgorithm.sort;

/**
 * 计数排序，命名来自于实现方法，跟计数有关
 * 计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数
 *
 * 是桶排序的一种特殊情况，假设有n个数据，所处的范围并不大时，令最大值为K，我们可以分为K个桶，这样桶内的数据都是一样的，不需要排序，之后按编号合并桶到数组中就好
 * 时间复杂度是线性的，即是O(n)
 * 适合数据范围分布不大的数据，数据量比较多的场景 比如1000万考生高考成绩排名。
 * 
 * @author LiYiGuang
 * @date 2020/1/16 10:05
 */
public class CountingSort {
	/**
	 * 计数排序 假设排序的是正整数
     * 1.找最大值max， 2.设桶，桶的个数为max + 1，下标为 0~max
	 * 3.桶C的元素为各个数据的个数，然后来个顺序求和，这样C[k]中存储的就是小于等于k的数字的个数
	 * 4.从后往前遍历数组A，假设取值为m，则取C[m]=n，这样数组R[n-1]=m,C[m]=C[m]-1,依次类推
	 * 5.当我们扫描完这个数组A，之后数组R就是从小到大排好的
	 * 6.复制数组R到数组
	 * @param arr 数组
	 * @param n 数组大小
	 */
	public static void countingSort(int[] arr, int n) {
		if (arr == null || arr.length != n || n == 1)
			return;
		int max = arr[0];
		for (int i = 1; i < n; i++) {
			if (max < arr[i])
				max = arr[i];
		}
		int[] bucket = new int[max + 1];
		for (int i = 0; i < n; i++) {
			bucket[arr[i]]++;
		}
		for (int i = 1; i < max + 1; i++) {
			bucket[i] = bucket[i] + bucket[i - 1];
		}

		int[] newArr = new int[n];
		for (int i = n - 1; i >= 0; i--) {
			int value = arr[i];
			int index = bucket[value] - 1;
			newArr[index] = value;
			bucket[value]--;
		}
		for (int i = 0; i < n; i++) {
			arr[i] = newArr[i];
		}
	}

	public static void print(int[] a, int n) {
		for (int i = 0; i < n; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 11, 8, 3, 9, 7, 1, 2, 5 };
		countingSort(arr, 8);
		print(arr, 8);
	}
}
